1. Field of the Invention
The present invention relates to task schedulers in operating systems for computing devices. In particular, the invention relates to schedulers for real-time operating systems.
2. Description of the Related Art
Real-time computing is becoming an increasingly important discipline. The operating system, and in particular the scheduler, is perhaps the most important component of a real-time system. Examples of current applications of real-time systems include control of laboratory experiments, process control plants, robotics, air traffic control, telecommunications, and military command and control systems. See generally William Stallings, OPERATING SYSTEMS: INTERNALS AND DESIGN PRINCIPLES 10-21, 129-32, 145-59, 384-99, 429-47 (3d ed. 1998) (hereinafter “Stallings”).
Scheduling in General
Before discussing, real-time scheduling, an introduction to scheduling algorithms for non-real-time systems will be given. The scheduling algorithms may be preemptive or nonpreemptive. According to Stallings, a nonpreemptive algorithm is when a running process continues to execute until it terminates or blocks itself to wait for I/O or by requesting some operating system service. A preemptive algorithm is when a running process that is currently executing may be interrupted and moved to the ready state by the operating system. The decision to preempt may be performed when a new process arrives, when an interrupt occurs that places a blocked process in the ready state, or periodically based on a clock interrupt.
Stallings also states that a scheduling algorithm may also include prioritization. Each process is assigned a priority and the scheduler will always choose a process of higher priority over one of lower priority. Such a scheme may be implemented with a number of ready queues, one for each priority level. When a process is ready it is placed in the appropriate queue. When the highest priority queue is empty the scheduler selects from the next highest priority queue.
Stallings lists six general types of scheduling algorithms: first-come first-served (FCFS), round robin, shortest process next (SPN), shortest remaining time (SRT), highest response ratio next (HRRN), and feedback.
The FCFS algorithm selects the process that has been waiting the longest for service as the next process. This may also be referred to as first-in, first-out. As each process becomes ready it is placed in the ready queue, and the oldest is selected when the system has completed the previous process. Stallings states that FCFS performs better for long processes than short ones, and that it tends to favor processor-bound processes over I/O-bound processes. Stallings states that an improved FCFS may be implemented with a priority scheme, with a number of priority levels and a ready queue for each priority level.
The round robin algorithm uses clocked preemption. The clock periodically generates an interrupt, upon which the currently running process is placed in the ready queue and the next ready process is selected on an FCFS basis. This may also be referred to as time slicing because each process is given a slice of time before being preempted. Stallings states that the principal design issue is the length of the time quantum, or slice, to be used. If the quantum is very short, then short processes will move through the system relatively quickly. On the other hand, there is processing overhead involved in handling the clock interrupt and in performing the scheduling and dispatching function. (More detail regarding this overhead is discussed below with reference to context switching.) Thus, Stallings concludes that very short time quanta should be avoided. Stallings states that one useful guide is that the time quantum should be slightly greater than the time required for a typical interaction. Stallings further states that a disadvantage to round robin is that processor-bound processes tend to receive an unfair portion of processor time as compared to I/O-bound processes.
The SPN algorithm is a nonpreemptive policy in which the process with the shortest expected processing time is selected next. One concern is that the required processing time of each process must be known or estimated.
The SRT algorithm is a preemptive version of SPN. If a new process joins the ready queue with a shorter known or expected completion time than the currently-executing process, the current process preempted and exchanged with the new process in the ready queue.
In HRRN, a response ratio is dynamically calculated for each process, and when the current process completes or is blocked, the ready process with the greatest response ratio value is selected as the next process to execute. The response ratio is the time the process has been waiting plus its known or estimated processing time, divided by the known or estimated processing time.
In feedback, the current process is interrupted periodically and is assigned to a lower priority queue. This results in a preference for newer, shorter processes, without having to know or estimate their processing times beforehand. The interrupt interval may be set longer for lower priority queues to help prevent starvation of a very long process. In addition, the priority of a process may be upgraded if it has not been executed for a while.
As mentioned above, whenever one process replaces another to be executed, a process switch (also called a context switch) is executed. Stallings states that in a process switch the operating system must make substantial changes in its environment, as follows. First, the context of the processor must be saved, including the program counter and other registers. Second, the process control block of the currently-running process must be updated, including changing the state of the process to another state and changing state information fields. Third, the process control block of this process must be moved to an appropriate other queue, such as the ready queue or the blocked queue. Fourth, another process must be selected and scheduled. Fifth, the process control block of the selected process must be updated. Sixth, the memory-management data structures may need to be updated, depending upon how address translation is managed. Seventh, the context of the processor must be restored to that which existed at the time the selected process was last switched out of the running state. Performing these changes requires overhead time, during which the processor cannot be used for running processes.
Real-Time Scheduling
Turning now to real-time scheduling, Stallings states that real-time computing may be defined as that type of computing in which the correctness of the system depends not only on the logical result of the computation, but also on the time at which the results are produced. We can define a real-time system by defining what is meant by a real-time process, or task. (As usual, terminology poses a problem, since various words are used in the literature with varying meanings. It is common for a particular process to operate under real-time constraints of a repetitive nature. That is, the process lasts for a long time and, during that time, performs some repetitive function in response to real-time events. Let us, for this section, refer to an individual function as a task. Thus, the process can be viewed as progressing through a sequence of tasks. At any given time, the process is engaged in a single task, and it is the process/task that must be scheduled.) In general, in a real-time system, some of the tasks are real-time tasks, and these have a certain degree of urgency to them. Such tasks are attempting to control or react to events that take place in the outside world. Because these events occur in “real time,” a real-time task must be able to keep up with the events with which it is concerned. Thus, it is usually possible to associate a deadline with a particular task, where the deadline specifies either a start time or a completion time. Such a task may be classified as hard or soft. A hard real-time task is one that must meet its deadline; otherwise it will cause undesirable damage or a fatal error to the system. A soft real-time task has an associated deadline that is desirable but not mandatory; it still makes sense to schedule and complete the task even if it has passed its deadline.
Stallings further states that another characteristic of real-time tasks is whether they are periodic or aperiodic. An aperiodic task has a deadline by which it must finish or start, or it may have a constraint on both start and finish time. In the case of a periodic task, the requirement may be stated as “once per period T” or “exactly T units apart.”
Characteristics of Real-Time Operating Systems
Stallings states that real-time operating systems can be characterized as having unique requirements in five general areas: determinism, responsiveness, user control, reliability, and fail-soft operation.
Stallings states that an operating system is deterministic to the extent that it performs operations at fixed, predetermined times or within predetermined time intervals. When multiple processes are competing for resources and processor time, no system will be fully deterministic. In a real-time operating system, process requests for service are dictated by external events and timings. The extent to which an operating system can deterministically satisfy requests depends first on the speed with which it can respond to interrupts and, second, on whether the system has sufficient capacity to handle all requests within the required time.
Stallings further states that one useful measure of the ability of an operating system to function deterministically is the maximum delay from the arrival of a high-priority device interrupt to when servicing begins. In non-real-time operating systems, this delay may be in the range of tens to hundreds of milliseconds, while in real-time operating systems that delay may have an upper bound of anywhere from a few microseconds to a millisecond.
Stallings also states that a related but distinct characteristic is responsiveness. Determinism is concerned with how long an operating system delays before acknowledging an interrupt. Responsiveness is concerned with how long, after acknowledgment, it takes an operating system to service the interrupt. Aspects of responsiveness include the following:
1. The amount of time required to initially handle the interrupt and begin execution of the interrupt service routine (ISR). If execution of the ISR requires a process switch, then the delay will be longer than if the ISR can be executed within the context of the current process.
2. The amount of time required to perform the ISR. This generally is dependent upon the hardware platform.
3. The effect of interrupt nesting. If an ISR can be interrupted by the arrival of another interrupt, then the service will be delayed.
Stallings still further states that determinism and responsiveness together make up the response time to external events. Response time requirements are critical for real-time systems, because such systems must meet timing requirements imposed by individuals, devices, and data flows external to the system.
Stallings states that user control is generally much broader in a real-time operating system than in ordinary operating systems. In a real-time system, it is essential to allow the user fine-grained control over task priority. The user should be able to distinguish between hard and soft tasks and to specify relative priorities within each class. A real-time system may also allow the user to specify such characteristics as the use of paging or process swapping, what processes must always be resident in main memory, what disk transfer algorithms are to be used, what rights the processes in various priority bands have, and so on.
Stallings also states that reliability is typically far more important for real-time systems than non-real-time systems.
Stallings further states that fail-soft operation is a characteristic that refers to the capability of a system to fail in such a way as to preserve as much capability and data as possible. When a real-time system detects a failure, it will attempt either to correct the problem or minimize its effects while continuing to run. A related concept is stability, which means that in cases where it is impossible to meet all task deadlines, the system will meet the deadlines of its most critical, highest-priority tasks, even it some less critical task deadlines are not always met.
Stallings states that current real-time systems typically include the following features:
1. Fast process or thread switch
2. Small size (with its associated minimal functionality)
3. Ability to respond to external interrupts quickly
4. Multitasking with interprocess communication tools such as semaphores, signals, and events
5. Use of special sequential files that can accumulate data at a fast rate
6. Preemptive scheduling based on priority
7. Minimization of intervals during which interrupts are disabled
8. Primitives to delay tasks for a fixed amount of time and to pause/resume tasks
9. Special alarms and timeouts.
Stallings asserts that the heart of a real-time system is the short-term task scheduler. In designing such a scheduler, fairness and minimizing average response time are not important. What is important is that all hard real-time tasks complete (or start) by their deadline and that as many as possible soft real-time tasks also complete (or start) by their deadline.
Stallings states that most contemporary real-time operating systems are unable to deal directly with deadlines. Instead, they are designed to be as responsive as possible to real-time tasks so that when a deadline approaches, a task can be quickly scheduled. From this point of view, real-time applications typically require deterministic response times in the several-millisecond to submillisecond span under a broad set of conditions; leading-edge applications—in simulators for military aircraft, for example—often have constraints in the range of 10 to 100 μs.
Stallings provides the following description with reference to FIGS. 1A-1D to illustrate a spectrum of possibilities. In a preemptive scheduler that uses simple round-robin scheduling, a real-time task would be added to the ready queue to await its next time slice, as illustrated in FIG. 1A. In this case, the scheduling time will generally be unacceptable for real-time applications. Alternatively, in a nonpreemptive scheduler, we could use a priority scheduling mechanism, giving real-time tasks higher priority. In this case, a real-time task that is ready would be scheduled as soon as the current process blocks or runs to completion (see FIG. 1B). This could lead to a delay of several seconds if a slow, low-priority task were executing at a critical time. Again, this approach is not acceptable. A more promising approach is to combine priorities with clock-based interrupts. Preemption points occur at regular intervals. When a preemption point occurs, the currently running task is preempted if a higher-priority task is waiting. This would include the preemption of tasks that are part of the operating system kernel. Such a delay may be on the order of several milliseconds (see FIG. 1C). While this last approach may be adequate for some real-time applications, it will not suffice for more demanding applications. In those cases, the approach that has been taken is sometimes referred to as immediate preemption (see FIG. 1D). In this case, the operating system responds to an interrupt almost immediately, unless the system is in a critical-code lockout section. Scheduling delays for a real-time task can then be reduced to 100 μs or less.
Stallings reports that a survey of real-time scheduling algorithms observes that the various scheduling approaches depend on (1) whether a system performs schedulability analysis, (2) if it does, whether it is done statically or dynamically, and (3) whether the result of the analysis itself produces a schedule or plan according to which tasks are dispatched at run time. Based on these considerations, the survey identifies the following classes of algorithms:
1. Static table-driven approaches: These perform a static analysis of feasible schedules of dispatching. The result of the analysis is a schedule that determines, at run time, when a task must begin execution.
2. Static priority-driven preemptive approaches: Again, a static analysis is performed, but no schedule is drawn up. Rather, the analysis is used to assign priorities to tasks, so that a traditional priority-driven preemptive scheduler can be used.
3. Dynamic planning-based approaches: Feasibility is determined at run time (dynamically) rather than offline prior to the start of execution (statically). An arriving task is accepted for execution only if it is feasible to meet its time constraints. One of the results of the feasibility analysis is a schedule or plan that is used to decide when to dispatch this task.
4. Dynamic best effort approaches: No feasibility analysis is performed. The system tries to meet all deadlines and aborts any started process whose deadline is missed.
Stallings states that static table-driven scheduling is applicable to tasks that are periodic. Input to the analysis consists of the periodic arrival time, execution time, period ending deadline, and relative priority of each task. The scheduler attempts to develop a schedule that enables it to meet the requirements of all periodic tasks. This is a predictable approach but one that is inflexible, because any change to any task requirements requires that the schedule be redone. Earliest-deadline-first or other periodic deadline techniques (discussed later) are typical of this category of scheduling algorithms.
Stallings further states that static priority-driven preemptive scheduling makes use of the priority-driven preemptive scheduling mechanism common to most non-real-time multiprogramming systems. In a non-real-time system, a variety of factors might be used to determine priority. For example, in a time-sharing system, the priority of a process changes depending on whether it is processor bound or I/O bound. In a real-time system, priority assignment is related to the time constraints associated with each task. One example of this approach is the rate monotonic algorithm (discussed later), which assigns static priorities to tasks based on their periods.
Stallings yet further states that with dynamic planning-based scheduling, after a task arrives, but before its execution begins, an attempt is made to create a schedule that contains the previously scheduled tasks as well as the new arrival. If the new arrival can be scheduled in such a way that its deadlines are satisfied and that no currently scheduled task misses a deadline, then the schedule is revised to accommodate the new task.
Stallings also states that dynamic best effort scheduling is the approach used by many real-time systems that are currently commercially available. When a task arrives, the system assigns a priority based on the characteristics of the task. Some form of deadline scheduling, such as earliest-deadline scheduling, is typically used. Typically, the tasks are aperiodic and so no static scheduling analysis is possible. With this type of scheduling, until a deadline arrives or until the task completes, we do not know whether a timing constraint will be met. This is the major disadvantage of this form of scheduling. Its advantage is that it is easy to implement.
Stallings reports that two popular classes of real-time scheduling algorithms are deadline scheduling and rate monotonic scheduling.
Deadline Scheduling
Stallings states that most contemporary real-time operating systems are designed with the objective of starting real-time tasks as rapidly as possible, and hence emphasize rapid interrupt handling and task dispatching. In fact, this is not a particularly useful metric in evaluating real-time operating systems. Real-time applications are generally not concerned with sheer speed but rather with completing (or starting) tasks at the most valuable times, neither too early nor too late, despite dynamic resource demands and conflicts, processing overloads, and hardware or software faults. It follows that priorities provide a crude tool and do not capture the requirement of completion (or initiation) at the most valuable time.
Stallings reports that in recent years, there have been a number of proposals for more powerful and appropriate approaches to real-time task scheduling. All of these are based on having additional information about each task. In its most general form, the following information about each task might be used:
1. Ready time: Time at which task becomes ready for execution. In the case of a repetitive or periodic task, this is actually a sequence of times that is known in advance. In the case of an aperiodic task, this time may be known in advance, or the operating system may only be aware when the task is actually ready.
2. Starting deadline: Time by which a task must begin.
3. Completion deadline: Time by which task must be completed. The typical real-time application will either have starting deadlines or completion dead-lines, but not both.
4. Processing time: Time required to execute the task to completion. In some cases, this is supplied. In others, the operating system measures an exponential average. For still other scheduling systems, this information is not used.
5. Resource requirements: Set of resources (other than the processor) required by the task while it is executing.
6. Priority: Measures relative importance of the task. Hard real-time tasks may have an “absolute” priority, with the system failing if a deadline is missed. If the system is to continue to run no matter what, then both hard and soft real—time tasks may be assigned relative priorities as a guide to the scheduler.
7. Subtask structure: A task may be decomposed into a mandatory subtask and an optional subtask. Only the mandatory subtask possesses a hard deadline.
Stallings further states that there are several dimensions to the real-time scheduling function when deadlines are taken into account: which task to schedule next, and what sort of preemption is allowed. It can be shown, for a given preemption strategy and using either starting or completion deadlines, that a policy of scheduling the task with the earliest deadline minimizes the fraction of tasks that miss their deadlines. This conclusion holds both for single processor and multiprocessor configurations.
Stallings asserts that the other critical design issue is that of preemption. When starting deadlines are specified, then a nonpreemptive scheduler makes sense. In this case, it would be the responsibility of the real-time task to block itself after completing the mandatory or critical portion of its execution, allowing other real-time starting deadlines to be satisfied. This fits the pattern of FIG. 1B. For a system with completion deadlines, a preemptive strategy (FIG. 1C or 1D) is most appropriate. For example, if task X is running and task Y is ready, there may be circumstances in which the only way to allow both X and Y to meet their completion deadlines is to preempt X, execute Y to completion, and then resume X to completion.
Stallings states that a straightforward scheme is always to schedule the ready task with earliest deadline and let that task run to completion. When this approach is used, when a new task requires immediate service, the service is denied. This is the risk in dealing with aperiodic tasks, especially with starting deadlines. A refinement of the policy will improve performance if deadlines can be known in advance of the time that a task is ready. This policy, referred to as earliest deadline with unforced idle times, operates as follows: Always schedule the eligible task with the earliest deadline and let that task run to completion. An eligible task may not be ready, and this may result in the processor remaining idle even though there are ready tasks. The result is that, even though the processor is not used to maximum efficiency, all scheduling requirements are met.
Rate Monotonic Scheduling
Stallings states that one of the more promising methods of resolving multitask scheduling conflicts for periodic tasks is rate monotonic scheduling (RMS). The scheme was first proposed in 1973 but has only recently gained popularity. RMS assigns priorities to tasks on the basis of their periods.
Stallings further states that in RMS, the task's period T is the amount of time between the arrival of one instance of the task and the arrival of the next instance of the task. A task's rate (in Hertz) is simply the inverse of its period (in seconds). Typically, the end of a task's period is also the task's hard deadline, although some tasks may have earlier deadlines. The execution (or computation) time C is the amount of processing time required for each occurrence of the task. It should be clear that in a uniprocessor system, the execution time must be no greater than the period (must have C≦T). If a periodic task is always run to completion—that is, if no instance of the task is ever denied service because of insufficient resources—then the utilization of the processor by this task is U=C/T.
Stallings also states that for RMS, the highest-priority task is the one with the shortest period, the second highest-priority task is the one with the second shortest period, and so on. When more than one task is available for execution, the one with the shortest period is serviced first. If we plot the priority of tasks as a function of their rate, the result is a monotonically increasing function; hence the name, rate monotonic scheduling.
Stallings still further states that it is possible to achieve greater overall processor utilization and therefore accommodate more periodic tasks with earliest deadline scheduling than with RMS. Nevertheless, RMS has been widely adopted for use in industrial applications, for the following reasons:
1. The performance difference is small in practice, where a utilization as high as 90% is often achieved.
2. Most hard real-time systems also have soft real-time components, such as certain noncritical displays and built-in self-tests that can execute at lower priority levels to absorb the processor time that is not used with RMS scheduling of hard real-time tasks.
3. Stability is easier to achieve with RMS. When a system cannot meet all deadlines because of overload or transient errors, the deadlines of essential tasks need to be guaranteed provided that this subset of tasks is schedulable. In a static priority assignment approach, one only needs to ensure that essential tasks have relatively high priorities. This can be done in RMS by structuring essential tasks to have short periods or by modifying the RMS priorities to account for essential tasks. With earliest deadline scheduling, a periodic task's priority changes from one period to another. This makes it more difficult to ensure that essential tasks meet their deadlines.
The SHIFT Programming Language
The SHIFT programming language is used for describing and simulating dynamic networks of hybrid automata. See generally Akash Deshpande, Aleks Gollu and Luigi Semenzato, The Shift Programming Language for Dynamic Networks of Hybrid Systems, IEEE TRANSACTIONS ON AUTOMATIC CONTROL (Special Issue on Hybrid Systems, April 1998). Such systems consist of components which can be created, interconnected and destroyed as the system evolves. Components exhibit hybrid behavior: continuous-time phases separated by instantaneous discrete-event transitions. Components may evolve independently, or they may interact through selected state variables and events. The interaction network itself may evolve. However, the SHIFT programming language is a simulation engine, and lacks a real-time scheduler.
Concerns with the Existing Art
Given the above state of the art, both for simulation and for real-time schedulers, a number of concerns exist. Each time a task is preempted to allow another task to run, the scheduler has to switch contexts, which includes saving all processor registers, loading them for the new task, paging tasks in and out, etc. These context switches are overhead that introduce inefficiency in the execution.
Further, practical implementations of task schedulers in operating systems limit the simultaneous execution of tasks to some relatively small number (200-300). This reduces the scale of the application.
To reduce the overhead, it is known that function calls are cheaper in terms of system resource usage than context switching. This suggests that function calls may be used in place of context switches. But the problem is that function calls are nonpreemptive. That is, once a function starts, it cannot be interrupted until it is completed. (On the other hand, task scheduling is preemptive—tasks can be interrupted at any point to allow other tasks to run.) Being nonpreemptive, if a long function is being executed, it will delay other functions that are waiting to be executed, possibly violating their real-time deadlines. Due to this major drawback, function calls are not presently used for context switching.